Understanding the memory mechanism that enables Linked Lists.
- The dynamic structure of the Linked List relies entirely on **explicit references**—the `next` field in our Node_Structure is fundamentally a pointer.
- To fully utilize this flexibility for dynamic insertion and deletion in $O(1)$ time, we must first understand how pointers function at the memory level.
- A **pointer** is a variable whose value is the memory address of another variable.
- This mechanism allows nodes, physically scattered across memory, to be logically connected in a sequence.
- Pointers are essential for:
- **Dynamic Memory Allocation**: Requesting memory for new nodes at runtime.
- **Data Structure Linking**: Maintaining the sequential order using the `next` reference (e.g., $p$, $q$, $tmp$ variables used for traversal).
Core Operators (C/C++ Context)
| Operator | Name | Function |
|---|---|---|
| `&` | Address-of Operator | Returns the memory address of a variable. (e.g., `p = &x;`) |
| `*` | Dereference Operator | Accesses the value stored at the address contained in the pointer. (e.g., `value = *p;`) |